#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
// trie
struct trie_prefix_count{
    static const int SIZE=1E4+10;
    int trie[SIZE][26], tot=1; int ed[SIZE];
    void insert(char* str){
        int len=strlen(str), p=1;
        for(int k=0;k<len;k++){
            int ch=str[k]-'a';
            if(trie[p][ch]==0) trie[p][ch]=++tot;
            p=trie[p][ch];
        }
        ed[p]++;
    }
    int search(char* str){
        int len=strlen(str),p=1;
        int ans=0;
        for(int k=0;k<len;k++){
            p=trie[p][str[k]-'a'];
            if (p==0) return ans;
            ans+=ed[p];
        } return ans;
    }
    int main(){
        int n,m; cin>>n>>m; char str[SIZE];
        for(int i=1;i<=n;i++){scanf("%s",str); insert(str);}
        for(int i=1;i<=m;i++){scanf("%s",str); printf("%d\n",search(str));}
    }
};
// uf
struct uf_parity_game{
    struct{int l,r,ans;}query[110];
    int a[210],fa[210],d[210],n,m,t;
    void read_discrete(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            char str[5];
            scanf("%d%d%s",&query[i].l,&query[i].r,str);
            query[i].ans=(str[0]=='o'?1:0);
            a[++t]=query[i].l-1;
            a[++t]=query[i].r;
        }
        sort(a+1,a+t-1);
        n=unique(a+1,a+t+1)-a-1;
    }
    int get(int x){
        if(x==fa[x]) return x;
        int root=get(fa[x]);
        d[x]^=d[fa[x]];
        return fa[x]=root;
    }
    int main(){
        read_discrete();
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++){
            int x=lower_bound(a+1,a+n+1,query[i].l-1)-a;
            int y=lower_bound(a+1,a+n+1,query[i].r)-a;
            int p=get(x),q=get(y);
            if(p==q){
                if((d[x]^d[y])!=query[i].ans){
                    cout<<i-1<<endl; return 0;
                }
            } else {
                fa[p]=q; d[p]=d[x]^d[y]^query[i].ans;
            }
        } cout<<m<<endl;
    }
};
// treeList segmentTree Block
struct treeList_simple_number_problem{
    static const int SIZE=1e4+10;
    int n,m, a[SIZE];
    long long c[2][SIZE], sum[SIZE];
    long long ask(int k,int x){
        long long ans=0;
        for(;x;x-=x&-x) ans+=c[k][x];
        return ans;
    }
    void add(int k,int x,int y){
        for(;x<=n;x+=x&-x)c[k][x]+=y;
    }
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i];}
        while(m--){
            char op[2]; int l,r,d; scanf("%s%d%d",op,&l,&r);
            if(op[0]=='C'){
                scanf("%d",&d);
                add(0,l,d);add(0,r+1,-d);add(1,l,l*d);add(1,r+1,-(r+1)*d);
            }
            else {
                long long ans=sum[r]+(r+1)*ask(0,r)-ask(1,r);
                ans-=sum[l-1]+l*ask(0,l-1)-ask(1,l-1);
                printf("%lld\n",ans);
            }
        }
    }
};
// seg
struct seg_simple_number_problem{
    static const int SIZE=1e4+10;
    struct SegmentTree{
        int l,r;
        long long sum,add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
    }tree[SIZE*4];
    int a[SIZE],n,m;
    void build(int p,int l,int r)//No.p, [l,r]
    {
        l(p)=l,r(p)=r;
        if(l==r) { sum(p)=a[l]; return; }
        int mid=(l+r)/2;
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
        sum(p)=sum(p*2)+sum(p*2+1);
    }
    void spread(int p)
    {
        if(add(p))
        {
            sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
            sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
            add(p*2)+=add(p);
            add(p*2+1)+=add(p);
            add(p)=0;
        }
    }

    void change(int p,int l,int r,int z)
    {
        if(l<=l(p)&&r>=r(p))
        {
            sum(p)+=(long long)z*(r(p)-l(p)+1);
            add(p)+=z;
            return;
        }
        spread(p);
        int mid=(l(p)+r(p))/2;
        if(l<=mid) change(p*2,l,r,z);
        if(r>mid) change(p*2+1,l,r,z);
        sum(p)=sum(p*2)+sum(p*2+1);
    }

    long long ask(int p,int l,int r)
    {
        if(l<=l(p)&&r>=r(p)) return sum(p);
        spread(p);
        int mid=(l(p)+r(p))/2;
        long long ans=0;
        if(l<=mid) ans+=ask(p*2,l,r);
        if(r>mid) ans+=ask(p*2+1,l,r);
        return ans;
    }
    int main(){
        cin>>n>>m; for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        build(1,1,n);
        while(m--){
            char op[2]; int x,y,z; scanf("%s%d%d",op,&x,&y);
            if(op[0]=='C') {scanf("%d",&z); change(1,x,y,z);}
            else printf("%I64d\n",ask(1,x,y));
        }
    }
};
//block
struct block_simple_number_problem{
    static const int SIZE=1E4+10;
    long long a[SIZE], sum[SIZE], add[SIZE];
    int L[SIZE], R[SIZE]; // 每段左右端点
    int pos[SIZE]; // 每个位置属于哪一段
    int n, m, t;
    void change(int l,int r,long long d){
        int p=pos[l],q=pos[r];
        if(p==q){
            for(int i=l;i<=r;i++)a[i]+=d;
            sum[p]+=d*(r-l+1);
        } else {
            for(int i=p+1;i<=q-1;i++)add[i]+=d;
            for(int i=l;i<=R[p];i++)a[i]+=d;
            sum[p]+=d*(R[p]-l+1);
            for(int i=L[q];i<=r;i++)a[i]+=d;
            sum[q]+=d*(r-L[q]+1);
        }
    }
    long long ask(int l,int r){
        int p=pos[l],q=pos[r]; long long ans=0;
        if(p==q){
            for(int i=l;i<=r;i++) ans+=a[i];
            ans+=add[p]*(r-l+1);
        } else {
            for(int i=p+1;i<=q-1;i++)
                ans+=sum[i]+add[i]*(R[i]-L[i]+1);
            for(int i=l;i<=R[p];i++)ans+=a[i];
            ans+=add[p]*(R[p]-l+1);
            for(int i=L[q];i<=r;i++)ans+=a[i];
            ans+=add[q]*(r-L[q]+1);
        }
        return ans;
    }
    int main(){
        cin>>n>>m; for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        // 分块
        t=sqrt(n*1.0);
        for(int i=1;i<=t;i++){
            L[i]=(i-1)*sqrt(n*1.0)+1;
            R[i]=i*sqrt(n*1.0);
        }
        if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
        // 预处理
        for(int i=1;i<=t;i++){
            for(int j=L[i];j<=R[i];j++){
                pos[j]=i; sum[i]+=a[j];
            }
        }
        // 指令
        while(m--){
            char op[3]; int l,r,d; scanf("%s%d%d",op,&l,&r);
            if(op[0]=='C'){scanf("%d",&d); change(l,r,d);}
            else printf("%lld\n",ask(l,r));
        }
    }
};
// persist segmentTree
struct persist_seg_kth{
    static const int N=1e3+10, INF=1e9;
    struct SegmentTree {
        int lc, rc; // 左右子节点编号
        int sum;
    } tree[N * 20];
    int n, m, t, tot, a[N], b[N], root[N];

    int build(int l, int r) {
        int p = ++tot; // 新建一个节点，编号为p，代表当前区间[l,r]
        tree[p].sum = 0;
        if (l == r) return p;
        int mid = (l + r) >> 1;
        tree[p].lc = build(l, mid);
        tree[p].rc = build(mid + 1, r);
        return p;
    }

    int insert(int now, int l, int r, int x, int delta) {
        int p = ++tot;
        tree[p] = tree[now]; // 新建一个副本
        if (l == r) {
            tree[p].sum += delta; // 在副本上修改
            return p;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) tree[p].lc = insert(tree[now].lc, l, mid, x, delta);
        else tree[p].rc = insert(tree[now].rc, mid + 1, r, x, delta);
        tree[p].sum = tree[tree[p].lc].sum + tree[tree[p].rc].sum;
        return p;
    }

    int ask(int p, int q, int l, int r, int k) {
        if (l == r) return l; // 找到答案
        int mid = (l + r) >> 1;
        int lcnt = tree[tree[p].lc].sum - tree[tree[q].lc].sum; // 值在[l,mid]中的数有多少个
        if (k <= lcnt) return ask(tree[p].lc, tree[q].lc, l, mid, k);
        else return ask(tree[p].rc, tree[q].rc, mid + 1, r, k - lcnt);
    }
    int main(){
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            b[++t] = a[i];
        }
        sort(b + 1, b + t + 1); // 离散化
        t = unique(b + 1, b + t + 1) - (b + 1);
        root[0] = build(1, t); // 关于离散化后的值域建树
        for (int i = 1; i <= n; i++) {
            int x = lower_bound(b + 1, b + t + 1, a[i]) - b; // 离散化后的值
            root[i] = insert(root[i - 1], 1, t, x, 1); // 值为x的数增加1个
        }
        for (int i = 1; i <= m; i++) {
            int l, r, k; scanf("%d%d%d", &l, &r, &k);
            int ans = ask(root[r], root[l - 1], 1, t, k);
            printf("%d\n", b[ans]); // 从离散化后的值变回原值
        }
    }
};
// offline divide
struct offline_divede_conquer{
    static const int N=1e4+10, INF=1e9;
    int n,m,t,c[N],ans[N];
    struct rec{int op,x,y,z;}q[2*N],lq[2*N],rq[2*N];
    int ask(int x){
        int y=0; for(;x;x-=x&-x)y+=c[x];
        return y;
    }
    void change(int x,int y){
        for(;x<=n;x+=x&-x) c[x]+=y;
    }
    void solve(int lval,int rval,int st,int ed){
        if(st>ed)return;
        if(lval==rval){
            for(int i=st;i<=ed;i++) if(q[i].op>0)ans[q[i].op]=lval;
            return;
        }
        int mid=(lval+rval)>>1; int lt=0,rt=0;
        for(int i=st;i<=ed;i++){
            if(q[i].op==0){
                if(q[i].y<=mid)change(q[i].x,1),lq[++lt]=q[i];
                else rq[++rt]=q[i];
            } else {
                int cnt=ask(q[i].y)-ask(q[i].x-1);
                if(cnt>=q[i].z) lq[++lt]=q[i];
                else q[i].z-=cnt, rq[++rt]=q[i];
            }
        }
        for(int i=ed;i>=st;i--){
            if(q[i].op==0&&q[i].y<=mid)
                change(q[i].x,-1);
        }
        for(int i=1;i<=lt;i++)q[st+i-1]=lq[i];
        for(int i=1;i<=rt;i++)q[st+lt+i-1]=rq[i];
        solve(lval,mid,st,st+lt-1);
        solve(mid+1,rval,st+lt,ed);
    }
    int main(){
        cin>>n>>m; for(int i=1;i<=n;i++){int val; scanf("%d",&val); q[++t].op=0,q[t].x=i,q[t].y=val;}
        for(int i=1;i<=m;i++){int l,r,k; scanf("%d%d%d",&l,&r,&k); q[++t].op=i,q[t].x=l,q[t].y=r,q[t].z=k;}
        solve(-INF,INF,1,t);
        for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
    }
};

// 质数 约数 同余 矩阵乘法(高斯消元与线性空间) 组合计数 容斥原理 概率(数学期望)
// math pow nCr
// struct 内执行有误
struct math_nCr_pigword{
    const int a[4]={2,3,4679,35617};
    int p[36000],b[4],n,g,ans,i,j,x,y,mod=999911658;

    int power(int a,int b)
    {
        int c=1;
        for(;b;b>>=1)
        {
            if(b&1) c=(ll)c*a%mod;
            a=(ll)a*a%mod;
        }
        return c;
    }

    void exgcd(int a,int b,int &x,int &y)
    {
        if(!b) {x=1,y=0; return;}
        exgcd(b,a%b,x,y);
        int z=x; x=y; y=z-y*(a/b);
    }

    int inv(int a,int p)
    {
        int x,y;
        exgcd(a,p,x,y);
        return (x%p+p)%p;
    }

    int calc(int x,int mod)
    {
        int ans=1,y,a,b;
        for(y=n;x;x/=mod,y/=mod)
        {
            a=x%mod,b=y%mod;
            ans=(ll)ans*p[b]%mod*inv(p[a],mod)%mod*inv(b<a?0:p[b-a],mod)%mod;
        }
        return ans;
    }

    int main()
    {
        cin>>n>>g;
        g%=mod+1;
        if(!g) {cout<<"0\n"; return 0;}
        for(p[0]=i=1;i<=a[3];i++) p[i]=(ll)p[i-1]*i%mod;
        for(i=1;i*i<=n;i++)
            if(n%i==0)
            {
                for(j=0;j<4;j++) b[j]=(b[j]+calc(i,a[j]))%a[j];
                if(i*i!=n)
                    for(j=0;j<4;j++) b[j]=(b[j]+calc(n/i,a[j]))%a[j];
            }
        for(i=0;i<4;i++)
        {
            exgcd(mod/a[i],a[i],x,y);
            ans=(ans+(ll)x*(mod/a[i])%mod*b[i])%mod;
        }
        ans=(ans+mod)%mod,mod++;
        ans=power(g,ans);
        cout<<ans<<endl;
        return 0;
    }
};
// math pow
struct math_same_mod_luckiest_number{
    ll L,d,k,p,s,i,num=0;
    ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
    ll ksc(ll a,ll b,ll c){
        ll ans=0;
        while(b){
            if(b&1) ans=(ans+a)%c;
            a=a*2%c;
            b>>=1;
        } return ans;
    }
    ll ksm(ll a,ll b,ll c){
        ll ans=1%c; a%=c;
        while(b){
            if(b&1)ans=ksc(ans,a,c);
            a=ksc(a,a,c);
            b>>=1;
        } return ans;
    }
    ll phi(ll n){
        ll ans=n;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                ans=ans/i*(i-1);
                while(n%i==0)n/=i;
            }
        }
        if(n>1)ans=ans/n*(n-1);
        return ans;
    }
    ll number(){
        d=gcd(L,8ll); k=9*L/d;
        if(gcd(k,10ll)!=1)return 0;
        p=phi(k); s=sqrt(p);
        for(int i=1;i<=s;i++)
            if(p%i==0&&ksm(10ll,i,k)==1) return i;
        for(int i=s-1;i;i--)
            if(p%i==0&&ksm(10ll,p/i,k)==1) return p/i;
        return 0;
    }
    int main(){
        while(cin>>L&&L){printf("Case %lld: %lld\n",++num,number());}
    }
};
// math matrix multiply
struct math_matrix_multiply_fib{
    const int mod=1e4; int n;
    void mul(int f[2],int a[2][2]){
        int c[2]; memset(c,0,sizeof(c));
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                c[j]=(c[j]+(ll)f[k]*a[k][j])%mod;
        memcpy(f,c,sizeof(c));
    }
    void mulself(int a[2][2]){
        int c[2][2];
        memset(c,0,sizeof(c));
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    c[i][j]=(c[i][j]+(ll)a[i][k]*a[k][j])%mod;
        memcpy(a,c,sizeof(c));
    }
    int main(){
        while(cin>>n&&n!=-1){
            int f[2]={0,1}; int a[2][2]={{0,1},{1,1}};
            for(;n;n>>=1){
                if(n&1)mul(f,a);
                mulself(a);
            } cout<<f[0]<<endl;
        }
    }

};

// 最短路 最小生成树 lca/diameter tarjan bipartite flow
struct graph_lca{
};
struct graph_diameter_run{
    static const int SIZE = 3e3+10;
    int ver[SIZE * 2], Next[SIZE * 2], head[SIZE], tot;
    int f[SIZE][20], d[SIZE], w[SIZE], v[SIZE];
    int c1[SIZE * 2], c2[SIZE * 2], ans[SIZE];
    int n, m, t;
    queue<int> q;
    vector<int> a1[SIZE], b1[SIZE], a2[SIZE], b2[SIZE];

    void add_(int x, int y) {
            ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
    }

    void bfs() {
        t = log(n) / log(2);
        q.push(1); d[1] = 1;
        while (q.size()) {
            int x = q.front(); q.pop();
            for (int i = head[x]; i; i = Next[i]) {
                int y = ver[i];
                if (d[y]) continue;
                d[y] = d[x] + 1;
                f[y][0] = x;
                for (int j = 1; j <= t; j++)
                    f[y][j] = f[f[y][j - 1]][j - 1];
                q.push(y);
            }
        }
    }

    int lca(int x, int y) {
        if (d[x] > d[y]) swap(x, y);
        for (int i = t; i >= 0; i--)
            if (d[f[y][i]] >= d[x]) y = f[y][i];
        if (x == y) return x;
        for (int i = t; i >= 0; i--)
            if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
        return f[x][0];
    }

    void dfs(int x) {
        int val1 = c1[d[x] + w[x]], val2 = c2[w[x] - d[x] + n];
        v[x] = 1;
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if (v[y]) continue;
            dfs(y);
        }
        for (int i = 0; i < a1[x].size(); i++) c1[a1[x][i]]++;
        for (int i = 0; i < b1[x].size(); i++) c1[b1[x][i]]--;
        for (int i = 0; i < a2[x].size(); i++) c2[a2[x][i] + n]++;
        for (int i = 0; i < b2[x].size(); i++) c2[b2[x][i] + n]--;
        ans[x] += c1[d[x] + w[x]] - val1 + c2[w[x] - d[x] + n] - val2;
    }

    int main() {
        cin >> n >> m;
        for (int i = 1; i < n; i++) {
            int x, y; scanf("%d%d", &x, &y);
            add_(x, y), add_(y, x);
        }
        for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
        bfs();
        for (int i = 1; i <= m; i++) {
            int x, y; scanf("%d%d", &x, &y);
            int z = lca(x, y);
            a1[x].push_back(d[x]);
            b1[f[z][0]].push_back(d[x]);
            a2[y].push_back(d[x] - 2 * d[z]);
            b2[z].push_back(d[x] - 2 * d[z]);
        }
        dfs(1);
        for (int i = 1; i < n; i++) printf("%d ", ans[i]);
        printf("%d\n", ans[n]);
    }
};
struct graph_tarjan_blo{
    static const int N = 1e4+10, M = 5e4+10;
    int head[N], ver[M * 2], Next[M * 2];
    int dfn[N], low[N], Size[N];
    long long ans[N];
    bool cut[N];
    int n, m, tot, num;

    void add_(int x, int y) {
            ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
    }

    void tarjan(int x) {
        dfn[x] = low[x] = ++num;
        Size[x] = 1;
        int flag = 0, sum = 0;
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if (!dfn[y]) {
                tarjan(y);
                Size[x] += Size[y];
                low[x] = min(low[x], low[y]);
                if (low[y] >= dfn[x]) {
                    flag++;
                    ans[x] += (long long)Size[y] * (n - Size[y]);
                    sum += Size[y];
                    if (x != 1 || flag > 1) cut[x] = true;
                }
            }
            else low[x] = min(low[x], dfn[y]);
        }
        if (cut[x])
            ans[x] += (long long)(n - sum - 1)*(sum + 1) + (n - 1);
        else
            ans[x] = 2 * (n - 1);
    }

    int main() {
        cin >> n >> m;
        tot = 1;
        for (int i = 1; i <= m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (x == y) continue;
            add_(x, y), add_(y, x);
        }
        tarjan(1);
        for (int i = 1; i <= n; i++)
            printf("%lld\n", ans[i]);
    }
};
struct graph_bipartite_theft{
    static const int N = 2e3+6, M = 2e4+6;
    struct P {
        int x, y, z;
        bool operator < (const P w) const {
            return z > w.z;
        }
    } p[M];
    int n, m, v[N];
    vector<pair<int, int> > e[N];

    bool dfs(int x, int color) {
        v[x] = color;
        for (unsigned int i = 0; i < e[x].size(); i++) {
            int y = e[x][i].first;
            if (v[y]) {
                if (v[y] == color) return 0;
            } else {
                if (!dfs(y, 3 - color)) return 0;
            }
        }
        return 1;
    }

    inline bool pd(int now) {
        for (int i = 1; i <= n; i++) e[i].clear();
        for (int i = 1; i <= m; i++) {
            if (p[i].z <= now) break;
            e[p[i].x].push_back(make_pair(p[i].y, p[i].z));
            e[p[i].y].push_back(make_pair(p[i].x, p[i].z));
        }
        memset(v, 0, sizeof(v));
        for (int i = 1; i <= n; i++)
            if (!v[i] && !dfs(i, 1)) return 0;
        return 1;
    }

    int main() {
        cin >> n >> m;
        for (int i = 1; i <= m; i++)
            scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].z);
        sort(p + 1, p + m + 1);
        int l = 0, r = p[1].z;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (pd(mid)) r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
        return 0;
    }

};
struct graph_netflow_dance_night{
    static const int inf = 0x3fffffff, u = 4e3+10, w = 3e4+10;
    int head[u], now[u], ver[w], edge[w], Next[w], d[u], e[w], c[u], sta[u], ins[u], dfn[u], low[u];
    int n, m, p, s, t, i, j, tot, maxflow, ans, x, y, scc, st, num;
    char str[10];
    vector<int> a[u];
    queue<int> q;

    void add_(int x, int y, int z) {
            ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
            ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
    }

    bool bfs() { // 在残量网络上构造分层图
        memset(d, 0, sizeof(d));
        while (q.size()) q.pop();
        q.push(s); d[s] = 1; now[s] = head[s];
        while (q.size()) {
            int x = q.front(); q.pop();
            for (int i = head[x]; i; i = Next[i])
                if (edge[i] && !d[ver[i]]) {
                    q.push(ver[i]);
                    now[ver[i]] = head[ver[i]];
                    d[ver[i]] = d[x] + 1;
                    if (ver[i] == t) return 1;
                }
        }
        return 0;
    }

    int dinic(int x, int flow) { // 在当前分层图上增广
        if (x == t) return flow;
        int rest = flow, k, i;
        for (i = now[x]; i && rest; i = Next[i]) {
            now[x] = i; // 当前弧优化（避免重复遍历从x出发不可扩展的边）
            if (edge[i] && d[ver[i]] == d[x] + 1) {
                k = dinic(ver[i], min(rest, edge[i]));
                if (!k) d[ver[i]] = 0; // 剪枝，去掉增广完毕的点
                edge[i] -= k;
                edge[i ^ 1] += k;
                rest -= k;
            }
        }
        return flow - rest;
    }

    void add2(int x, int y)
    {
        a[x].push_back(y);
    }

    void tarjan(int x)
    {
        dfn[x] = ++num; low[x] = num;
        sta[++st] = x; ins[x] = 1;
        int y;
        for (int i = 0; i<a[x].size(); i++)
            if (!dfn[y = a[x][i]])
            {
                tarjan(y);
                low[x] = min(low[x], low[y]);
            }
            else if (ins[y]) low[x] = min(low[x], dfn[y]);
        if (dfn[x] == low[x])
        {
            scc++;
            do { y = sta[st]; st--; ins[y] = 0; c[y] = scc; } while (x != y);
        }
    }

    int main()
    {
        while (cin >> n >> m >> p)
        {
            memset(head, 0, sizeof(head));
            s = 0, t = n + m + 1; tot = 1; maxflow = 0;
            for (i = 1; i <= n; i++) add_(s, i, 1);
            for (i = 1; i <= m; i++) add_(i + n, t, 1);
            for (i = 1; i <= p; i++)
            {
                scanf("%d%d", &x, &y);
                add_(x, n + y, 1), e[i] = tot;
            }
            while (bfs())
                while (i = dinic(s, inf)) maxflow += i;
            for (i = s; i <= t; i++) a[i].clear();
            for (i = 1; i <= p; i++)
                if (!edge[e[i]]) add2(ver[e[i]], ver[e[i] ^ 1]);
                else add2(ver[e[i] ^ 1], ver[e[i]]);
            for (i = 1; i <= n; i++)
                if (!edge[2 * i]) add2(i, s); else add2(s, i);
            for (i = 1; i <= m; i++)
                if (!edge[2 * (n + i)]) add2(t, n + i); else add2(n + i, t);
            memset(dfn, 0, sizeof(dfn));
            memset(ins, 0, sizeof(ins));
            memset(c, 0, sizeof(c));
            st = num = scc = ans = 0;
            for (i = s; i <= t; i++)
                if (!dfn[i]) tarjan(i);
            for (i = 1; i <= p; i++)
                if (edge[e[i]] || c[ver[e[i]]] == c[ver[e[i] ^ 1]]) ans++;
            cout << (ans = p - ans) << endl;
            if (!ans) cout << endl;
            for (i = 1; i <= p; i++)
                if (!edge[e[i]] && c[ver[e[i]]] != c[ver[e[i] ^ 1]])
                    if (--ans) printf("%d ", i); else printf("%d\n", i);
        }
    }
};
// bfs-shortestPath
struct graph_shortestPath_trade{
    static const int MAX_N = 1e3+5, MAX_M = 1e4+5;
    int head[MAX_N], ver[MAX_M], edge[MAX_M], nxt[MAX_M], tot;
    int n, m, a[MAX_N], d[MAX_N]/*前缀min*/, f[MAX_N]/*后缀max*/;
    bool v[MAX_N]; // 点是否在队列中
    queue<int> q;

    void add_(int x, int y, int z) {
            tot++;
            ver[tot] = y;
            edge[tot] = z; // 1表示只能正着走，-1表示只能倒着走，2表示正反都可以
            nxt[tot] = head[x];
            head[x] = tot;
    }
// 求d数组，从st出发，只有标记为z和2的边可以用
    void spfa(int* d, int st, int z) {
        d[st] = a[st];
        q.push(st); v[st] = true;
        while (!q.empty()) {
            int x = q.front();
            q.pop(); v[x] = false;
            for (int i = head[x]; i; i = nxt[i])
                if (edge[i] == z || edge[i] == 2) {
                    int y = ver[i];
                    int val = z == 1 ? min(d[x], a[y]) : max(d[x], a[y]);
                    if (z == 1 && d[y] > val || z == -1 && d[y] < val) {
                        d[y] = val;
                        if (!v[y]) { q.push(y); v[y] = true; }
                    }
                }
        }
    }
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= m; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add_(x, y, z);
            add_(y, x, z == 1 ? -1 : z);
        }
        memset(d, 0x3f, sizeof(d));
        spfa(d, 1, 1); // 从1出发求前缀min（d），只有1和2的边可以用
        memset(f, 0xcf, sizeof(f));
        spfa(f, n, -1); // 从n出发倒着求后缀max（d），只有-1和2的边可以用
        int ans = 0;
        for (int i = 1; i <= n; i++) ans = max(ans, f[i] - d[i]);
        cout << ans << endl;
    }
};
// bfs-minGenerateTree
struct graph_minGenerateTree_castle{
    const __int64 mod = (1LL << 31) - 1;
    const int mi = 199311170;
    int mat[1010][1010], n; static int dist[1010]; bool sign[1010];
    void ginit (void)
    {
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) mat[i][j] = mi;
        for (int i = 0; i < n; i++) mat[i][i] = 0;
    }
    void glink (int a, int b, int l)
    {
        mat[a][b] = mat[b][a] = min(mat[a][b], l);
    }
    void dijkstra (void)
    {
        for (int i = 0; i < n; i++) dist[i] = mi, sign[i] = false;
        dist[0] = 0;
        for (int i = 0; i < n; i++)
        {
            int cur = -1;
            for (int j = 0; j < n; j++)
            {
                if (!sign[j])
                {
                    if (cur == -1 || dist[j] < dist[cur]) cur = j;
                }
            }
            sign[cur] = true;
            for (int j = 0; j < n; j++)
            {
                if (!sign[j])
                {
                    if (dist[j] > dist[cur] + mat[cur][j]) dist[j] = dist[cur] + mat[cur][j];
                }
            }
        }
    }
    int list[1010]; __int64 ans = 1;
    static bool comp (const int& a, const int& b)
    {
        return dist[a] < dist[b];
    }
    int main ()
    {
//        freopen("castle.in", "r", stdin);
//        freopen("castle.out", "w", stdout);
        int m; scanf("%d %d", &n, &m);
        ginit();
        for (int i = 0; i < m; i++)
        {
            int x, y, l; scanf("%d %d %d", &x, &y, &l);
            glink(x - 1, y - 1, l);
        }
        dijkstra();
        for (int i = 0; i < n; i++) list[i] = i;
        sort(list, list + n, comp);
        for (int i = 1; i < n; i++)
        {
            int tt = 0;
            for (int j = 0; j < i; j++)
            {
                if (dist[list[j]] + mat[list[j]][list[i]] == dist[list[i]]) ++tt;
            }
            ans = (ans * tt) % mod;
        }
        printf("%I64d\n", ans);
//        fclose(stdin);
//        fclose(stdout);
        return 0;
    }
};

// bfs-gameAstar
namespace eight_puzzle_Astar{
// state：八数码的状态(3*3九宫格压缩为一个整数)
// dist：当前代价 + 估价
    struct rec{int state,dist;
        rec(){}
        rec(int s,int d){state=s,dist=d;}
    };
    int a[3][3];
// map和priority_queue的用法参见0x71节C++ STL
    map<int,int> d,f,go;
    priority_queue<rec> q;
    const int dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
    char dir[4]={'u','l','r','d'};

    bool operator <(rec a,rec b) {
        return a.dist>b.dist;
    }

// 把3*3的九宫格压缩为一个整数（9进制）
    int calc(int a[3][3]) {
        int val=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++) {
                val=val*9+a[i][j];
            }
        return val;
    }

// 从一个9进制数复原出3*3的九宫格，以及空格位置
    pair<int,int> recover(int val,int a[3][3]) {
        int x,y;
        for(int i=2;i>=0;i--)
            for(int j=2;j>=0;j--) {
                a[i][j]=val%9;
                val/=9;
                if(a[i][j]==0) x=i,y=j;
            }
        return make_pair(x,y);
    }

// 计算估价函数
    int value(int a[3][3]) {
        int val=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++) {
                if(a[i][j]==0) continue;
                int x=(a[i][j]-1)/3;
                int y=(a[i][j]-1)%3;
                val+=abs(i-x)+abs(j-y);
            }
        return val;
    }

// A*算法
    int astar(int sx,int sy,int e) {
        d.clear(); f.clear(); go.clear();
        while(q.size()) q.pop();
        int start=calc(a);
        d[start]=0;
        q.push(rec(start,0+value(a)));
        while(q.size()) {
            // 取出堆顶
            int now=q.top().state; q.pop();
            // 第一次取出目标状态时，得到答案
            if(now==e) return d[now];
            int a[3][3];
            // 复原九宫格
            pair<int,int> space=recover(now,a);
            int x=space.first,y=space.second;
            // 枚举空格的移动方向（上下左右）
            for(int i=0;i<4;i++) {
                int nx=x+dx[i], ny=y+dy[i];
                if (nx<0||nx>2||ny<0||ny>2) continue;
                swap(a[x][y],a[nx][ny]);
                int next=calc(a);
                // next状态没有访问过，或者能被更新
                if(d.find(next)==d.end()||d[next]>d[now]+1) {
                    d[next]=d[now]+1;
                    // f和go记录移动的路线，以便输出方案
                    f[next]=now;
                    go[next]=i;
                    // 入堆
                    q.push(rec(next,d[next]+value(a)));
                }
                swap(a[x][y],a[nx][ny]);
            }
        }
        return -1;
    }

    void print(int e) {
        if(f.find(e)==f.end()) return;
        print(f[e]);
        putchar(dir[go[e]]);
    }

    int main() {
        int end=0;
        for(int i=1;i<=8;i++) end=end*9+i;
        end*=9;
        int x,y;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++) {
                char str[2];
                scanf("%s",str);
                if(str[0]=='x') a[i][j]=0,x=i,y=j;
                else a[i][j]=str[0]-'0';
            }
        int ans=astar(x,y,end);
        if(ans==-1) puts("unsolvable"); else print(end);
    }
};
struct eight_puzzle_IDAstar{
    string st, ed;
    int depth, ans[50];
    int hfunc(string st) {
        int ans = 0;
        for (int i = 0; i < st.size(); ++i) {
            if (st[i] == '0') continue;
            int j = ed.find(st[i]), r = i / 3, c = i % 3;
            int x = j / 3, y = j % 3;
            ans += abs(r - x) + abs(c - y);
        }
        return ans;
    }
    const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}, step[4] = {'u', 'l', 'd', 'r'};
    bool dfs(int now, int pre) {
        int cnt = hfunc(st);
        if (!cnt) return 1;
        if (now + cnt > depth) return 0;
        int pos = st.find('0'), x = pos / 3, y = pos % 3;
        for ( int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || nx * 3 + ny == pre) continue;
            swap(st[pos], st[nx * 3 + ny]);
            ans[now + 1] = step[i];
            if (dfs(now + 1, pos)) return 1;
            swap(st[pos], st[nx * 3 + ny]);
        }
        return 0;
    }
    int main() {
        for ( int i = 1; i <= 9; ++i) {
            char s[2];
            scanf("%s", s);
            st += s[0] == 'x' ? '0' : s[0];
        }
        int cnt = 0;
        for ( int i = 0; i < st.size(); ++i)
            if (st[i] != '0')
                for ( int j = 0; j < i; ++j)
                    if (st[j] != '0') cnt += st[i] > st[j];
        if (cnt & 1) {
            puts("unsolvable");
            return 0;
        }
        ed = "123456780";
        for (depth = hfunc(st); !dfs(0, -1); ++depth);
        for ( int i = 1; i <= depth; ++i)
            putchar(ans[i]);
    }
};
int main(){
    // ds
    trie_prefix_count t;t.main();
//    uf_parity_game u;u.main();

//    treeList_simple_number_problem t;t.main();
//    seg_simple_number_problem s;s.main();
//    block_simple_number_problem b;b.main();

//    persist_seg_kth p;p.main();

//    offline_divede_conquer o;o.main();

    // math
//    math_nCr_pigword m;m.main();
//    math_same_mod_luckiest_number m;m.main();
//    math_matrix_multiply_fib m;m.main();

    // bfs 8-puzzle
//    eight_puzzle_Astar e;e.main();
//    eight_puzzle_IDAstar e;e.main();

    // graph
//    graph_shortestPath_trade g;g.main();
//    graph_minGenerateTree_castle g;g.main();

//    graph_diameter_run g;g.main();
//    graph_base_ring_freda g;g.main();
//    graph_tarjan_blo g;g.main();
//    graph_bipartite_theft g;g.main();
//    graph_netflow_dance_night g;g.main();

}